#include <stdio.h>

#define ElementType int
#define MAXN 100

void merge_pass(ElementType list[],ElementType sorted[],int N,int length);

void output(ElementType list[],int N)
{
    int i;
    for(i=0;i<N;i++) printf("%d ",list[i]);
    printf("\n");
}

void merge_sort(ElementType list[],int N)
{
    ElementType extra[MAXN];  /* the extra space required */
    int         length=1;  /* current length of sublist being merged */
    while(length<N)
    {
        merge_pass(list,extra,N,length); /* merge list into extra */
        output(extra,N);
        length*=2;
        merge_pass(extra,list,N,length); /* merge extra back to list */
        output(list,N);
        length*=2;
    }
}


int main()
{
    freopen("6-1.in","r",stdin);
    int         N,i;
    ElementType A[MAXN];
    
    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);
    merge_sort(A,N);
    output(A,N);
    
    return 0;
}

/* Your function will be put here */
void merge_pass(ElementType list[],ElementType sorted[],int N,int length)
{
    for(int i=0;i<N;)
    {
        int start1=i;
        int start2=i+length;
        int num   =i;
        int last  =(i+2*length>=N)?N:i+2*length;
        
        int j=start1,k=start2;
        for(;j<start2&&k<last;)
            if(list[j]<=list[k])
                sorted[num]=list[j],++j,++num;
            else
                sorted[num]=list[k],++k,++num;
        for(;j<start2;sorted[num]=list[j],++j,++num);
        for(;k<last;sorted[num]=list[k],++k,++num);
        i+=2*length;
    }
}